package leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author:xufengxiang
 * @date 2023-04-03 19:50
 */
public class Code20 {

    public static boolean isValid(String s) {
        int length = s.length();

        Map<Character,Character> brackets = new HashMap<>();
        brackets.put('(',')');
        brackets.put('{','}');
        brackets.put('[',']');
        //todo：添加冗余字符，避免list取空。
        brackets.put('?','?');
        if(length <=1 || !brackets.containsKey(s.charAt(0))){
            return false;
        }

        LinkedList<Character> list = new LinkedList<>();
        list.addLast('?');
        for(int i=0;i< length;i++){
            char c = s.charAt(i);
            if(brackets.containsKey(c)){
                list.addLast(c);
            }else{
                Character last = list.removeLast();
                Character character = brackets.get(last);
                if(!character.equals(c)){
                    return false;
                }
            }
        }
        return list.size() == 1;
    }

    public static void main(String[] args) {
        System.out.println(isValid("()[]{}"));
    }


}
